package algorithm.structure.tree.b;

import algorithm.structure.tree.util.TreeTool;

public class BTreeSYT {
	private BTreeNodeSYT root = BTreeNodeSYT.AllocateNode();
	
	public SearchResult searchNode(BTreeNodeSYT x,int k){
		
		int i = 1;
		int n = x.getN();
		while(i <= n && k > x.getKey(i)){
			i = i + 1;
		}
		if(i <= n && x.getKey(i) == k){
			SearchResult result = new SearchResult();
			result.setNode(x);
			result.setX(i);
			return result;
		}else if(x.isLeaf()){
			return null;
		}else{
			return searchNode(x,k);
		}
	}
	
	
	
	public BTreeNodeSYT getRoot() {
		return root;
	}



	public void setRoot(BTreeNodeSYT root) {
		this.root = root;
	}

	public void splitChild(BTreeNodeSYT x,int i){
		BTreeNodeSYT z = BTreeNodeSYT.AllocateNode();
		BTreeNodeSYT y = x.getChildren(i);
		int t = BTreeNodeSYT.DEGREE;
		z.setLeaf(y.isLeaf());
		z.setN(t - 1);
		for(int j=1; j<=t-1;j++){
			z.setKeys(j,y.getKey(j+t));
		}
		for(int j=1; j<=t;j++){
			z.setChildren(j, y.getChildren(j));
		}
		if(!y.isLeaf()){
			for(int j=1;j<=t;j++){
				z.setChildren(j,y.getChildren(j+t));
			}
			for(int j=1;j<=t;j++){
				y.setChildren(j+t, null);
			}
		}
		
		for(int j=x.getN()+1;j>=i+1;i--){
			x.setChildren(j+1,x.getChildren(j));
		}
		x.setChildren(i+1, z);
		for(int j=x.getN();j>=i;i--){
			x.setKeys(j, x.getKey(j));
		}
		x.setKeys(i, y.getKey(t));
		x.setN(x.getN() + 1);
		y.setN(t-1);
	}
	
	
	public void insert(int k){
		BTreeNodeSYT r = root;
		int t = BTreeNodeSYT.DEGREE;
		if(r.getN() == (2*t - 1)){
			BTreeNodeSYT s = BTreeNodeSYT.AllocateNode();
			root = s;
			s.setLeaf(false);
			s.setN(0);
			s.setChildren(1,r);
			splitChild(s,1);
			insertNonFull(s,k);
		}else{
			insertNonFull(r,k);
		}
	}
	public void insertNonFull(BTreeNodeSYT x,int k){
		int i = x.getN();
		int t = BTreeNodeSYT.DEGREE;
		if(x.isLeaf()){
			while(i>=1 && k<x.getKey(i)){
				x.setKeys(i+1, x.getKey(i));
				i--;
			}
			x.setKeys(i+1, k);
			x.setN(x.getN() + 1);
		}else{
			while(i>=1 && k<x.getKey(i)){
				i--;
			}
			i++;
			if(x.getChildren(i).getN() == (2*t-1)){
				splitChild(x,i);
				if(k>x.getKey(i)){
					i++;
				}
			}
			insertNonFull(x.getChildren(i),k);
		}
	}
	
	public void deleteNode(int k){
		BTreeNodeSYT r = root;
		if(r.getN() == 1 && !r.isLeaf()){
			BTreeNodeSYT y = r.getChildren(1);
			BTreeNodeSYT z = r.getChildren(2);
			if(y.getN() == BTreeNodeSYT.DEGREE - 1 && z.getN() == BTreeNodeSYT.DEGREE - 1){
				mergeChild(r,1,y,z);
				r = y;
				root = y;
			}
		}else if(r.getN() == 0){
			return;
		}
		deleteNode(r,k);
	}
	
	private void deleteNode(BTreeNodeSYT x, int k){
		int i = 1;
		while(i<=x.getN() && k > x.getKey(i)){
			i++;
		}
		if(x.isLeaf()){
			if(i>x.getN()){
				try{
					throw new RuntimeException("Not Find:10");
				}catch(Exception e){
					e.printStackTrace();
				}
			}else{
				if(x.getKey(i) == k){
					for(int j = i; j <= x.getN(); j++){
						x.setKeys(j, x.getKey(j+1));
					}
					x.setN(x.getN()-1);
				}
			}
		}else{
			if(i<=x.getN() && x.getKey(i) == k){
				BTreeNodeSYT y = x.getChildren(i);
				BTreeNodeSYT z = x.getChildren(i + 1);
				if(y.getN()>=BTreeNodeSYT.DEGREE){
					k = searchPredecessor(y);
					x.setKeys(i,k);
					deleteNode(y,k);
				}else if(z.getN()>=BTreeNodeSYT.DEGREE){
					k = searchSuccessor(z);
					x.setKeys(i,k);
					deleteNode(z,k);
				}else if((z.getN() == BTreeNodeSYT.DEGREE-1) &&(z.getN() == BTreeNodeSYT.DEGREE-1)){
					mergeChild(x,i,y,z);
					deleteNode(y,k);
				}else{
					try{
						throw new RuntimeException("Bad Tree:7");
					}catch(Exception e){
						e.printStackTrace();
					}
				}
			}else{
				BTreeNodeSYT c = x.getChildren(i);
				BTreeNodeSYT y;
				BTreeNodeSYT z;
				if(c.getN() == BTreeNodeSYT.DEGREE-1){
					if(i==1){
						z = x.getChildren(i+1);
						if(z.getN()>=BTreeNodeSYT.DEGREE){
							shiftToLeftChild(x,i, c,z);
						}else if(z.getN() == BTreeNodeSYT.DEGREE-1){
							mergeChild(x,i,c,z);
						}else{
							try{
								throw new RuntimeException("Bad Tree:8");
							}catch(Exception e){
								e.printStackTrace();
							}
						}
					}else if(i==x.getN()+1){
						y = x.getChildren(i-1);
						if(y.getN()>=BTreeNodeSYT.DEGREE){
							shiftToRightChild(x, i-1, c, y);
						}else if(y.getN() == BTreeNodeSYT.DEGREE-1){
							mergeChild(x,i-1,y,c);
							c = y;
						}else{
							try{
								throw new RuntimeException("Bad Tree:9");
							}catch(Exception e){
								e.printStackTrace();
							}
						}
					}else{
						y = x.getChildren(i-1);
						z = x.getChildren(i+1);
						if(y.getN() == z.getN() && y.getN() == BTreeNodeSYT.DEGREE - 1){
							mergeChild(x,i,c,z);
						}else if(y.getN() >= BTreeNodeSYT.DEGREE){
							shiftToRightChild(x, i-1, c, y);
						}else if(z.getN() >= BTreeNodeSYT.DEGREE){
							shiftToLeftChild(x,i, c,z);
						}else{
							try{
								throw new RuntimeException("Bad Tree:10");
							}catch(Exception e){
								e.printStackTrace();
							}
						}
					}
				}else if(c.getN() < BTreeNodeSYT.DEGREE-1){
					try{
						throw new RuntimeException("Bad Tree:11");
					}catch(Exception e){
						e.printStackTrace();
					}
				}
				deleteNode(c,k);
			}
		}
	}
	
	
	
	private void mergeChild(BTreeNodeSYT x, int i, BTreeNodeSYT y, BTreeNodeSYT z){
		int t = BTreeNodeSYT.DEGREE;
		int xN = x.getN();
		y.setKeys(t, x.getKey(i));
		for(int j = t + 1; j <= 2 * t - 1; j++){
			y.setKeys(j, z.getKey(j-t));
		}
		if(!y.isLeaf()){
			for(int j = t + 1; j <= 2 * t; j++){
				y.setChildren(j, z.getChildren(j-t));
			}
		}
		x.setKeys(i,x.getKey(i+1));
		for(int j = i + 1; j <= x.getN(); j++){
			x.setChildren(j, x.getChildren(j + 1));
			x.setKeys(j,x.getKey(j + 1));
		}
		x.setChildren(xN + 1, null);
		x.setN(xN - 1);
		y.setN(2*t-1);
	}
	
	private int searchPredecessor(BTreeNodeSYT x){
		while(!x.isLeaf()){
			x = x.getChildren(x.getN());
		}
		return x.getKey(x.getN());
	}

	private int searchSuccessor(BTreeNodeSYT x){
		while(!x.isLeaf()){
			x = x.getChildren(1);
		}
		return x.getKey(1);
	}
	
	//y -> c 
	private void shiftToRightChild(BTreeNodeSYT x, int i, BTreeNodeSYT c, BTreeNodeSYT y){
		int cN = c.getN();
		int yN = y.getN();
		
		for(int j=cN;j>=1;j--){
			c.setKeys(j+1,c.getKey(j));
		}
		if(!c.isLeaf()){
			for(int j=cN+1;j>=1;j--){
				c.setChildren(j+1,c.getChildren(j));
			}
			c.setChildren(1,y.getChildren(yN+1));
			y.setChildren(yN+1, null);
		}
		c.setKeys(1, x.getKey(i));
		x.setKeys(i, y.getKey(yN));
		c.setN(cN + 1);
		y.setN(yN - 1);
	}
	
	//z -> c 
	private void shiftToLeftChild(BTreeNodeSYT x, int i, BTreeNodeSYT c, BTreeNodeSYT z){
		int cN = c.getN();
		int zN = z.getN();
		c.setKeys(cN+1, x.getKey(i));
		x.setKeys(i, z.getKey(1));
		if(!c.isLeaf()){
			c.setChildren(cN+2,z.getChildren(1));
		}
		for(int j=1;j<=zN;j++){
			z.setChildren(j, z.getChildren(j+1));
			z.setKeys(j, z.getKey(j+1));
		}
		z.setChildren(cN+2, null);
		c.setN(c.getN()+1);
		z.setN(zN - 1);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BTreeSYT tree = new BTreeSYT();
		tree.insert(1);
		tree.insert(2);
		tree.insert(3);
		tree.insert(4);
		tree.insert(5);
		tree.insert(6);
		tree.insert(7);
		tree.insert(8);
		tree.insert(9);
		tree.insert(10);
		tree.insert(11);
		tree.insert(12);
		tree.insert(13);
		tree.insert(14);
		tree.insert(15);
		tree.insert(16);
		System.out.println(TreeTool.getInstanse().getBTreeXml(tree));
	}
	
	static class SearchResult{
		private BTreeNodeSYT node;
		private int x;
		public BTreeNodeSYT getNode() {
			return node;
		}
		public void setNode(BTreeNodeSYT node) {
			this.node = node;
		}
		public int getX() {
			return x;
		}
		public void setX(int x) {
			this.x = x;
		}
	}
}
